package ms.sudoku;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import ms.sudoku.technique.EliminationTechnique;
import ms.sudoku.technique.NakedSingleTechnique;
import ms.sudoku.util.RandomHelper;

import org.lex.game.sudoku.model.Point;

import common.Difficulty;
import common.Sudokus;

//Description: A Sudoku puzzle generator.
public final class Generator {
	public static void main(String[] args) {
		GeneratorOptions opt = GeneratorOptions.create(Difficulty.Hard);
		Generator gen = new Generator(opt);
		PuzzleState state = gen.generate();
		System.out.println(state);
	}

	private GeneratorOptions options;

	public Generator(GeneratorOptions options) {
		if (options == null)
			options = GeneratorOptions.create(Difficulty.Easy);

		if (options.getPuzzlesCount() < 1)
			throw new RuntimeException("options");

		this.options = options;
	}

	/**
	 * Generates a random Sudoku puzzle.
	 */
	public PuzzleState generate() {
		// Generate the number of puzzles specified in the options and sort them
		// by difficulty
		List<SolverResults> puzzleSolveResults = new ArrayList<>();
		for (int i = 0; i < options.getPuzzlesCount(); i++) {
			puzzleSolveResults.add(generateOne());
		}

		/*
		 * Find the hardest puzzle from those generated and return it. NOTE: The
		 * puzzle may be easier than the numbers in the SolverResults would
		 * otherwise indicate. The generator runs each technique as much as
		 * possible before filling in a number, but filling in a number can
		 * actually make the puzzle solvable with fewer techniques.
		 */
		Collections.sort(puzzleSolveResults, new SolverResultsComparator(options.getAllowedTechniques()));
		return puzzleSolveResults.get(puzzleSolveResults.size() - 1).getPuzzle();
	}

	/**
	 * Generates a random Sudoku puzzle.
	 */
	private SolverResults generateOne() {
		/*
		 * Generate a full solution randomly, using the solver to solve a
		 * completely empty grid. For this, we'll use the elimination techniques
		 * that yield fast solving.
		 */
		PuzzleState solvedState = new PuzzleState(options.getBoxSize());
		SolverOptions solverOptions = new SolverOptions();
		solverOptions.setMaximumSolutionsToFind(1);
		solverOptions.getEliminationTechniques().add(new NakedSingleTechnique());
		solverOptions.setAllowBruteForce(true);
		SolverResults newSolution = Solver.solve(solvedState, solverOptions);

		/*
		 * Create options to use for removing filled cells from the complete
		 * solution. MaximumSolutionsToFind is set to 2 so that we look for more
		 * than 1, but there's no need in continuing once we know there's more
		 * than 1, so 2 is a fine value to use.
		 */
		solverOptions.setMaximumSolutionsToFind(2);
		solverOptions.setAllowBruteForce(options.getDecisionPoints() > 0);
		List<EliminationTechnique> techniques = null;
		if (solverOptions.getAllowBruteForce()) {
			techniques = new ArrayList<>();
			techniques.add(new NakedSingleTechnique());
		} else {
			techniques = this.options.getAllowedTechniques();
		}
		solverOptions.setEliminationTechniques(techniques);
		// For perf: if brute force is allowed, techniques don't matter!

		/*
		 * Now that we have a full solution, we want to randomly remove values
		 * from cells until we get to a point where there is not a unique
		 * solution for the puzzle. The last puzzle state that did have a unique
		 * solution can then be used.
		 */
		PuzzleState newPuzzle = newSolution.getPuzzle();
		Point[] filledCells = getRandomCellOrdering(newPuzzle);

		// Do we want to ensure symmetry?
		int filledCellCount = options.getEnsureSymmetry() && (filledCells.length % 2 != 0) ? filledCells.length - 1
				: filledCells.length;
		// If ensuring symmetry...
		if (options.getEnsureSymmetry()) {
			// Find the middle cell and put it at the end of the ordering
			for (int i = 0; i < filledCells.length - 1; i++) {
				Point p = filledCells[i];
				if (p.x == newPuzzle.getGridSize() - p.x - 1 && p.y == newPuzzle.getGridSize() - p.y - 1) {
					Point temp = filledCells[i];
					filledCells[i] = filledCells[filledCells.length - 1];
					filledCells[filledCells.length - 1] = temp;
				}
			}

			/*
			 * Modify the random ordering so that paired symmetric cells are
			 * next to each other. i.e. filledCells[i] and filledCells[i+1] are
			 * symmetric pairs
			 */
			for (int i = 0; i < filledCells.length - 1; i += 2) {
				Point p = filledCells[i];
				Point sp = new Point(newPuzzle.getGridSize() - p.x - 1, newPuzzle.getGridSize() - p.y - 1);
				for (int j = i + 1; j < filledCells.length; j++) {
					if (filledCells[j].equals(sp)) {
						Point temp = filledCells[i + 1];
						filledCells[i + 1] = filledCells[j];
						filledCells[j] = temp;
						break;
					}

				}
			}

			/*
			 * In the order of the array, try to remove each pair from the
			 * puzzle and see if it's still solvable and in a valid way. If it
			 * is, greedily leave those cells out of the puzzle. Otherwise, skip
			 * them.
			 */
			int[] oldValues = new int[2];
			for (int filledCellNum = 0; filledCellNum < filledCellCount
					&& newPuzzle.getFilledCellCount() > options.getMinFilledCells(); filledCellNum += 2) {
				/*
				 * Store the old value so we can put it back if necessary, then
				 * wipe it out of the cell
				 */
				oldValues[0] = newPuzzle.get(filledCells[filledCellNum]);
				oldValues[1] = newPuzzle.get(filledCells[filledCellNum + 1]);
				newPuzzle.setCell(filledCells[filledCellNum], Sudokus.EMPTY_NUMBER);
				newPuzzle.setCell(filledCells[filledCellNum + 1], Sudokus.EMPTY_NUMBER);

				/*
				 * Check to see whether removing it left us in a good position
				 * (i.e. a single-solution puzzle that doesn't violate any of
				 * the generation options)
				 */SolverResults newResults = Solver.solve(newPuzzle, solverOptions);
				if (!isValidRemoval(newPuzzle, newResults)) {
					newPuzzle.setCell(filledCells[filledCellNum], oldValues[0]);
					newPuzzle.setCell(filledCells[filledCellNum + 1], oldValues[1]);
				}

			}

			/*
			 * If there are an odd number of cells in the puzzle (which there
			 * will be as everything we're doing is 9x9, 81 cells), try to
			 * remove the odd cell that doesn't have a pairing. This will be the
			 * middle cell.
			 */
			if (filledCells.length % 2 != 0) {
				/*
				 * Store the old value so we can put it back if necessary, then
				 * wipe it out of the cell
				 */
				int filledCellNum = filledCells.length - 1;
				int oldValue = newPuzzle.get(filledCells[filledCellNum]);
				newPuzzle.setCell(filledCells[filledCellNum], Sudokus.EMPTY_NUMBER);

				/*
				 * Check to see whether removing it left us in a good position
				 * (i.e. a single-solution puzzle that doesn't violate any of
				 * the generation options)
				 */
				SolverResults newResults = Solver.solve(newPuzzle, solverOptions);
				if (!isValidRemoval(newPuzzle, newResults)) {
					newPuzzle.setCell(filledCells[filledCellNum], oldValue);
				}
			}
		} else {
			// otherwise, it's much easier.

			/*
			 * Look at each cell in the random ordering. Try to remove it. If it
			 * works to remove it, do so greedily. Otherwise, skip it.
			 */
			for (int filledCellNum = 0; filledCellNum < filledCellCount
					&& newPuzzle.getFilledCellCount() > options.getMinFilledCells(); filledCellNum++) {
				/*
				 * Store the old value so we can put it back if necessary, then
				 * wipe it out of the cell
				 */
				int oldValue = newPuzzle.get(filledCells[filledCellNum]);
				newPuzzle.setCell(filledCells[filledCellNum], Sudokus.EMPTY_NUMBER);

				/*
				 * Check to see whether removing it left us in a good position
				 * (i.e. a single-solution puzzle that doesn't violate any of
				 * the generation options)
				 */
				SolverResults newResults = Solver.solve(newPuzzle, solverOptions);
				if (!isValidRemoval(newPuzzle, newResults))
					newPuzzle.setCell(filledCells[filledCellNum], oldValue);

			}
		}

		// Make sure to now use the techniques specified by the user to score
		// this thing
		solverOptions.setEliminationTechniques(options.getAllowedTechniques());
		SolverResults finalResult = Solver.solve(newPuzzle, solverOptions);

		// Return the best puzzle we could come up with
		newPuzzle.setDifficulty(options.getDifficulty());
		return new SolverResults(PuzzleStatus.Solved, newPuzzle, finalResult.getNumberOfDecisionPoints(),
				finalResult.getUseOfTechniques());
	}

	/**
	 * Returns all cells in a collection in random order.
	 */
	private static Point[] getRandomCellOrdering(PuzzleState state) {
		// Create the collection
		Point[] points = new Point[state.getGridSize() * state.getGridSize()];
		// Find all cells
		int count = 0;
		for (int i = 0; i < state.getGridSize(); i++) {
			for (int j = 0; j < state.getGridSize(); j++) {
				points[count++] = new Point(i, j);
			}
		}

		RandomHelper rand = new RandomHelper();
		// Randomize their order
		for (int i = 0; i < points.length - 1; i++) {
			int swapPos = rand.getRandomNumber(i, points.length - 1);
			Point temp = points[swapPos];
			points[swapPos] = points[i];
			points[i] = temp;
		}
		// Return the randomized collection
		return points;
	}

	/**
	 * Determines whether the SolverResults created by solving a puzzle with a
	 * particular cell value removed represents a valid new state. Return true
	 * if the removal that led to this call is valid; otherwise, false.
	 * 
	 * @param state
	 * @param results
	 * @return
	 */
	private boolean isValidRemoval(PuzzleState state, SolverResults results) {
		// Make sure we have a puzzle with one and only one solution
		if (results.getStatus() != PuzzleStatus.Solved || results.getPuzzles().size() != 1) {
			return false;
		}

		// Make sure we don't have too few cells
		if (state.getFilledCellCount() < options.getMinFilledCells()) {
			return false;
		}

		// Now check to see if too many decision points were involved
		if (options.getDecisionPoints() > 0 && results.getNumberOfDecisionPoints() > options.getDecisionPoints()) {
			return false;
		}

		// Otherwise, it's a valid removal.
		return true;
	}
}
